/*
 * @(#)TourArray.java
 * 0.2 2011-12-22
 * 
 * Copyright (c) 2011 David Falk, Klaus Nicosia, Marcus Oberg.
 */

package logic;

import java.util.Arrays;

/**
 * Array implementation of the Tour datatype for TSP.
 * 
 * @author      Klaus Nicosia,
 * @author      David Falk,
 * @author      Marcus Oberg.
 */
public class TourArray implements Tour {
		
	/** Number of elements in the tour. */
	private Vertex[] tour;
	
	/** 
	 * Inverse of tour: City i is visited as number B[i].
	 * (A[B[i]] = city_i, 1 <= i <= N).
	 */
	private int[] tourInverse;

	/**
	 * Creates an empty tour of length size.
	 * 
	 * @param size	length of the tour to be created.
	 */
	public TourArray(int size) {
		tour = new Vertex[size];
		tourInverse = new int[size];
	}
	
	/**
	 * Creates an tour from the array of vertices t.
	 * 
	 * @param t	the array of vertices to create the tour from.
	 */
	private TourArray(Vertex[] t) {
		tour = new Vertex[t.length];
		tourInverse = new int[t.length];
		
		for (int i = 0; i < t.length; i++) {
			tour[i] = t[i];
			tourInverse[tour[i].index] = i;
		}
	}
	
	/**
	 * Creates an tour from the array of indexes and the graph that contains
	 * the vertices for those indexes.
	 * 
	 * @param t	the tour represented as an array indexes.
	 * @param g	the graph containing the vertices.
	 */
	public TourArray(int[] t, Graph g) {
		tour = new Vertex[t.length];
		tourInverse = new int[t.length];

		for (int i = 0; i < t.length; i++) {
			tour[i] = g.vertices[t[i]];
			tourInverse[tour[i].index] = i;
		}
	}
	
	/**
	 * Adds city to the tour at index.
	 * 
	 * @param city	city to add.
	 * @param index	index at which to add the city.
	 */
	public void addCity(Vertex city, int index) {
		if (index < 0) {
			throw new ArrayIndexOutOfBoundsException(
					"Index (" + index
					+ ") must be greater than or equal to 0 in addCity.");
		} else if (index >= tour.length) {
			throw new ArrayIndexOutOfBoundsException(
					"Index (" + index
					+ ") to large in addCity. Maximum is: "
					+ (tour.length - 1) + ".");
		} else {
			tour[index] = city;
			tourInverse[city.index] = index;

		}
	}

	/**
	 * Number of elements in the tour.
	 * 
	 * @return	the number of elements in the tour.
	 */
	public int size() {
		return tour.length;
	}
	
	/**
	 * Length of the tour: the distance to travel.
	 * 
	 * @return	the length of the tour.
	 */
	public int length() {
		int distance = 0;
		for (int i = 0; i < tour.length; i++) {
			if (i == tour.length - 1) {
				distance += tour[i].getEuclideanDistance(tour[0]);
			} else {
				distance += tour[i].getEuclideanDistance(tour[i + 1]);
			}
		}
		return distance;
	}
	
	/**
	 * This is a query that returns the city that follows a in the current
	 * tour.
	 * 
	 * @param a	the vertex for which the next one is returned.
	 * @return	the next city.
	 */
	public Vertex next(Vertex a) {
		int i = tourInverse[a.index]; // City a is visited as number i.
		
		if(i == tour.length - 1) { // Last city in the tour.
			return tour[0];
		} else {
			return tour[i + 1];
		}
	}
	
	/**
	 * This is a query that returns the city that precedes a in the current
	 * tour.
	 * 
	 * @param a	the vertex for which the previous one is returned.
	 * @return	the previous city.
	 */
	public Vertex prev(Vertex a) {
		int i = tourInverse[a.index]; // City a is visited as number i.
		
		if(i == 0) { // First city in the tour.
			return tour[tour.length - 1];
		} else {
			return tour[i - 1];
		}
	}
	
	/**
	 * This is a query that returns true if b is found before c in a traversal
	 * from a.
	 * 
	 * @param a	the vertex where the traversal is started.
	 * @param b	the vertex to be found first for a true result.
	 * @param c	the vertex where the traversal ended if no b is found.
	 * @return	true if vertex b was found before c and false if not.
	 */
	public boolean between(Vertex a, Vertex b, Vertex c) {
		int bcmp = tourInverse[b.index] - tourInverse[a.index];
		int ccmp = tourInverse[c.index] - tourInverse[a.index];
		if (bcmp < 0) {
			bcmp = tour.length + bcmp;
		}
		if (ccmp < 0) {
			ccmp = tour.length + ccmp;
		}
		if (bcmp < ccmp) {
			return true;
		}
		return false;
	}
	
	/**
	 * This updates the tour by replacing the edges (a, b) and (d, c) by the 
	 * edges (b, c) and (a, d). This operation assumes that b = Next(a) and 
	 * c = Next(d).
	 * 
	 * @param a	the first vertex in the first directed edge (a, b).
	 * @param b	the second vertex in the first directed edge (a, b).
	 * @param c	the second vertex in the second directed edge (d, c).
	 * @param d	the first vertex in the second directed edge (d, c).
	 */
	public void flip(Vertex a, Vertex b, Vertex c, Vertex d) {
		
		/* Growing index starts at index for city b in the tour. */
		int gIndex = tourInverse[b.index];
		
		/* Decreasing index starts at index for city d in the tour. */
		int dIndex = tourInverse[d.index];
		
		/* 
		 * If the distance between dIndex and gIndex is odd they will meet at
		 * the same index.
		 * 
		 * If the distance between dIndex and gIndex is even they will end up
		 * next to each other and then pass each other (swap indexes) at the
		 * next iteration.
		 * 
		 * Works even if b.index > d.index.
		 */
		while (dIndex != gIndex && !(dIndex == gIndex - 1)) {
			int tempI = gIndex;
			tourInverse[tour[gIndex].index] = dIndex;
			tourInverse[tour[dIndex].index] = tempI;
			
			Vertex tempV = tour[gIndex];
			tour[gIndex] = tour[dIndex];
			tour[dIndex] = tempV;

			gIndex += 1;
			dIndex -= 1;
			
			/* 
			 * gIndex has grown beyond the end of the array, change it to the
			 * start.
			 */
			if (gIndex > tour.length - 1) {
				gIndex = 0;
			}
			
			/*
			 * dIndex has decreased beyond the start of the array, change it to
			 * the end.
			 */
			if (dIndex < 0) {
				dIndex = tour.length - 1;
			}
		}
	}

	/**
	 * Returns the entire tour as an array of vertices.
	 * 
	 * @return	the tour as an array of vertices.
	 */
	public Vertex[] getTour() {
		return tour;
	}
	
	/**
	 * Returns the entire tour represented as a String.
	 * 
	 * @return	the tour represented as a String.
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < tour.length; i++) {
			sb.append(tour[i].index);
			if (i < tour.length - 1) {
				sb.append('\n');
			}
		}
		return sb.toString();
	}
	
	/**
	 * Returns the city at the specified index in the tour: the city to be
	 * visited as city number 'index'.
	 * 
	 * @param index	the index in the tour of the city to be returned.
	 * @return		the at the specified index in the tour.
	 */
	public Vertex getCity(int index) {
		return tour[index];
	}
	
	
	// +++++++++++++++++++
	// + TESTING SECTION +
	// +++++++++++++++++++
	public static void main(String[] args) {
		//addCityTest();
		threeOptTest();
	}

	/**
	 * Prints the tour array as A and the tourInverse array as B.
	 * For testing purposes.
	 */
	private void print() {
		System.out.print("A = [");
		for (int i = 0; i < tour.length - 1; i++) {
			System.out.print(tour[i].index + ", ");
		}
		System.out.println(tour[tour.length - 1].index+ "]");
		
		System.out.print("B = [");
		for (int i = 0; i < tourInverse.length - 1; i++) {
			System.out.print(tourInverse[i] + ", ");
		}
		System.out.println(tourInverse[tourInverse.length - 1] + "]");
	}
	
	/* TEMP: Test for addCity. */
	private static void addCityTest() {
		Vertex s = new Vertex(0, 0, 5);
		Vertex t = new Vertex(0, 0, 3);
		Vertex a = new Vertex(0, 0, 1);
		Vertex b = new Vertex(0, 0, 0);
		Vertex v = new Vertex(0, 0, 4);
		Vertex u = new Vertex(0, 0, 6);
		Vertex d = new Vertex(0, 0, 7);
		Vertex c = new Vertex(0, 0, 2);
		
		TourArray ta = new TourArray(8);
		ta.addCity(s, 0);
		ta.addCity(t, 1);
		ta.addCity(a, 2);
		ta.addCity(b, 3);
		ta.addCity(v, 4);
		ta.addCity(u, 5);
		ta.addCity(d, 6);
		ta.addCity(c, 7);
		ta.print();
	}
	
	/* TEMP: Test for 2-opt. */
	private static void twoOptTest() {
		Vertex s = new Vertex(0, 0, 5);
		Vertex t = new Vertex(0, 0, 3);
		Vertex a = new Vertex(0, 0, 1);
		Vertex b = new Vertex(0, 0, 0);
		Vertex v = new Vertex(0, 0, 4);
		Vertex u = new Vertex(0, 0, 6);
		Vertex d = new Vertex(0, 0, 7);
		Vertex c = new Vertex(0, 0, 2);
		Vertex[] tour = {s, t, a, b, v, u, d, c};
		TourArray ta = new TourArray(tour);
		a = ta.tour[2];
		b = ta.tour[3];
		c = ta.tour[7];
		d = ta.tour[6];
		
		System.out.println("Two-opt test");
		ta.print();
		System.out.println("Flip(" + a.index + ", " + b.index + ", " + c.index
				+ ", " + d.index + ")");
		ta.flip(a, b, c, d);
		ta.print();
	}
	
	/* TEMP: Test for 3-opt. */
	private static void threeOptTest() {
		System.out.println("\nThree-opt test");
		int[] result;	
		Vertex[] tour2 = {new Vertex(0, 0, 0),
				new Vertex(0, 0, 1),
				new Vertex(0, 0, 6),
				new Vertex(0, 0, 2),
				new Vertex(0, 0, 3),
				new Vertex(0, 0, 7),
				new Vertex(0, 0, 4),
				new Vertex(0, 0, 5),
				new Vertex(0, 0, 8)};
		
		TourArray ta = new TourArray(tour2);
		Vertex a = ta.tour[ta.tourInverse[0]];
		Vertex b = ta.tour[ta.tourInverse[1]];
		Vertex d = ta.tour[ta.tourInverse[2]];
		Vertex c = ta.tour[ta.tourInverse[3]];
		Vertex f = ta.tour[ta.tourInverse[4]];
		Vertex e = ta.tour[ta.tourInverse[5]];
		
		ta.print();
		
		System.out.println("Flip(" + a.index + ", " + b.index + ", " + c.index
				+ ", " + d.index + ")");
		ta.flip(a, b, c, d);

		System.out.println("Flip(" + a.index + ", " + d.index + ", " + e.index
				+ ", " + f.index + ")");
		ta.flip(a, d, e, f);
		ta.print();
		
		result = new int[ta.size()];
		for(int i=0;i<ta.size(); i++){
			result[i] = ta.tour[ta.tourInverse[i]].index;
		}
		System.out.println("Res: "+Arrays.toString(result));
	}
}